
/*
回溯
连接：https://leetcode.cn/problems/word-search/description/
题目：  单词搜索


    算法思路：
    我们需要假设每个位置的元素作为第⼀个字⺟，然后向相邻的四个⽅向进⾏递归，并且不能出现重复
    使⽤同⼀个位置的元素。通过深度优先搜索的⽅式，不断地枚举相邻元素作为下⼀个字⺟出现的可能
    性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。
    递归函数设计：bool dfs(int x, int y, int step, vector<vector<char>>& board, string word,
    vector<vector<bool>>& vis, int &n, int &m, int &len)
    参数：x（当前需要进⾏处理的元素横坐标），y（当前需要进⾏处理的元素横坐标），step（当前已
    经处理的元素个数），word（当前的字符串状态）；
    返回值：当前坐标元素作为字符串中下标 step 的元素出现是否可以找到成⽴的字符串。
    函数作⽤：判断当前坐标的元素作为字符串中下标 step 的元素出现时，向四个⽅向传递，查找是否存
    在路径结果与字符串相同。
    递归函数流程：
    1. 遍历每个位置，标记当前位置并将当前位置的字⺟作为⾸字⺟进⾏递归，并且在回溯时撤回标记。
    2. 在每个递归的状态中，我们维护⼀个步数 step，表⽰当前已经处理了⼏个字⺟。
    ◦ 若当前位置的字⺟与字符串中的第 step 个字⺟不相等，则返回 false。
    ◦ 若当前 step 的值与字符串⻓度相等，表⽰存在⼀种路径使得 word 成⽴，返回 true。
    3. 对当前位置的上下左右四个相邻位置进⾏递归，若递归结果为 true，则返回 true。
    4. 若相邻的四个位置的递归结果都为 false，则返回 false。
    • 特别地，如果使⽤将当前遍历到的字符赋值为空格，并在回溯时恢复为原来的字⺟的⽅法，则在递
    归时不会重复遍历当前元素，可达到不使⽤标记数组的⽬的。
    
*/
class Solution {
public:
    bool vis[7][7];//标记用了哪些字符，避免循环使用
    int m,n;//记录board的长宽
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==word[0])
                {
                    vis[i][j] = true;
                    if(dfs(board,i,j,word,1)) return true;
                    //以当前位置的字符进行匹配，并没有匹配成功
                    vis[i][j] = false;
                }
            }
        }
        //循环内部均未找到匹配成功的字符串，返回false
        return false;

    }
    //向量数组，记录寻找的坐标
    int r[4] = {0,0,-1,1};
    int c[4] = {-1,1,0,0};
    bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos)
    {
        //出口--找到最后一个word的字符了，说明匹配结束
        if(pos == word.size())
            return true;
        for(int k=0;k<4;k++)
        {
            int x = i+r[k];
            int y = j+c[k];
            if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && word[pos]==board[x][y]  )
            {
                vis[x][y] = true;
                if(dfs(board,x,y,word,pos+1)) return true;//此条路径找到了，直接返回
                vis[x][y] = false;
            }
        }
        //4个点都找了，没找到
        return false;
    }
};